package com.pan.alg.niuke.tree;

import java.util.Arrays;

/**
 * 描述 给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
 * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。
 *
 * <p>提示: 1.vin.length == pre.length 2.pre 和 vin 均无重复元素 3.vin出现的元素均出现在 pre里
 * 4.只需要返回根结点，系统会自动输出整颗树做答案对比 数据范围：n \le 2000n≤2000，节点的值 -10000 \le val \le 10000−10000≤val≤10000
 * 要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
 */
public class TreeReConstructBinaryTree {

    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {

        int prel = pre.length;
        int vinl = vin.length;
        if(prel==0||vinl==0){
            return null;
        }

        TreeNode head = new TreeNode(pre[0]);

        for(int i=0;i<vinl;i++){

            if(pre[0]==vin[i]){

                //构建左子树
                head.left=reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(vin,0,i));

                //构建右子树
                head.right=reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,prel),Arrays.copyOfRange(vin,i+1,vinl));
                break;
            }
        }

        return head;
    }

}
